package com.example.fina2202.day07;


public class BinarySearchTree<E extends Comparable<E>> {
    //根节点
    private Node root;

    //添加元素
    public boolean add(E e){
        //判断root是否为null
        if (root==null) {
            root = new Node(e);
            return true;
        }
        //root不为null
        return root.append(e);
    }

    //根据元素查询对应的节点对象
    public Node get(E e){
        //判断root是否为null
        if (root==null)
            return null;
        //root不为空,则判断root是否为目标节点
        return root.isDestNode(e);
    }

    //重写toString
    @Override
    public String toString() {
        //判断root是否为null,为null,返回"[]"
        if (root==null)
            return "[]";
        //进行中序遍历
        StringBuilder builder = new StringBuilder("[");
        return root.middleOrder(builder).replace(builder.length()-1,builder.length(),"]").toString();
    }

    //定义内部类表示节点
    private class Node{
        private E ele;  //节点中保存的元素对象
        private Node left;  //左子树指向的节点
        private Node right;  //右子树指向的节点

        //定义有参构造方法,用于创建节点
        Node(E ele){
            this.ele = ele;
        }

        //向某个节点上添加给定的元素,尝试让新元素称为其左/右子树
        public boolean append(E e) {
            //判断e和节点的元素是否相等,若相等,则添加失败,返回false
            if (e.compareTo(ele)==0)
                return false;
            else if(e.compareTo(ele)<0){  //尝试向ele的left上添加节点
                //判断left是否为null,为null,则让新元素成为left节点
                if (left==null) {
                    left = new Node(e);
                    return true;
                }
                return left.append(e);
            } else {  //尝试向ele的right添加节点
                if (right==null){
                    right = new Node(e);
                    return true;
                }
                return right.append(e);
            }
        }

        public StringBuilder middleOrder(StringBuilder builder) {
            //左
            if (left!=null){
                left.middleOrder(builder);
            }
            //取根的值
            builder.append(ele).append(",");
            //取右
            if (right!=null){
                right.middleOrder(builder);
            }
            //以上三步操作结束,得到遍历树后的元素拼接结果:[1,2,3,5,需要将最后的逗号替换为]
            return builder;
        }

        //用于判断调用方法的节点是否为目标节点
        public Node isDestNode(E e) {
            //判断e是否和当前节点的元素相等,若相等,说明为目标节点,返回当前节点即可
            if (e.compareTo(ele)==0)
                return this;
            else if (e.compareTo(ele)>0){  //e大于当前节点,到right上继续查找
                //若right为null,说明目标元素不存在树中,返回null
                if (right==null)
                    return null;
                return right.isDestNode(e);
            }else {  //e小于当前节点,到left上继续查找
                if (left==null)
                    return null;
                return left.isDestNode(e);
            }
        }
        //重写toString
        @Override
        public String toString() {
            return "Node{" +
                    "ele=" + ele +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }





}
